/*
 * @Author: szx
 * @Date: 2022-03-11 21:53:37
 * @LastEditTime: 2022-03-11 22:18:06
 * @Description:
 * @FilePath: \leetcode\2100-2199\2049\2049.js
 */
/**
 * @param {number[]} parents
 * @return {number}
 */
var countHighestScoreNodes = function (parents) {
    const n = parents.length;
    const children = new Array(n).fill(0).map(() => []);
    let maxScore = 0;
    let cnt = 0;
    for (let i = 0; i < n; i++) {
        const p = parents[i];
        if (p !== -1) children[p].push(i);
    }

    const dfs = (node) => {
        let score = 1;
        let sum = 1;
        for (const c of children[node]) {
            let t = dfs(c);
            score *= t;
            sum += t;
        }
        // 根节点上面那一坨
        if (node !== 0) {
            score *= n - sum;
        }
        if (score === maxScore) {
            cnt++;
        } else if (score > maxScore) {
            maxScore = score;
            cnt = 1;
        }
        return sum;
    };

    dfs(0);
    return cnt;
};
console.log(countHighestScoreNodes([-1, 2, 0, 2, 0]));

